package com.ttc.e9.paixu;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;

public class Tong {
	public static void bucketSort(int[] arr){
		int min=arr[0];
		int max=arr[0];
		for(int i=1;i<arr.length;i++){
			if(arr[i]>max){
				max=arr[i];
			}
			if(arr[i]<min){
				min=arr[i];
			}
		}
		
		ArrayList<ArrayList<Integer>> bucket=new ArrayList<>();
		int count=(max-min)/arr.length+1;
		for(int i=0;i<count;i++){
			bucket.add(new ArrayList<Integer>());
		}
		
		for(int i=0;i<arr.length;i++){
			bucket.get((arr[i]-min)/arr.length).add(arr[i]);
		}
		
		for(int i=0;i<bucket.size();i++){
			Collections.sort(bucket.get(i));
		}
		int k=0;
		for(int i=0;i<bucket.size();i++){
			ArrayList<Integer> list=bucket.get(i);
			for(int j=0;j<list.size();j++){
				arr[k++]=list.get(j);
			}
		}
	}
	public static void main(String[] args) {
		int[] arr={3,9,4,6,2,8,7,0,5};
		bucketSort(arr);
		System.out.println(Arrays.toString(arr));
		
	}

}
